package listbyorder.access101_200.test188;

import java.util.*;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/15 11:01
 */
public class Solution4 {

    class Transaction {
        int valley;
        int peek;

        Transaction(int v, int p) {
            valley = v;
            peek = p;
        }
    }

    public int maxProfit(int k, int[] prices) {
        if(k == 0){
            return 0;
        }
        Stack<Transaction> stack = new Stack<>();
        List<Integer> profit = new ArrayList<>();
        int v;
        int p = -1;
        int n = prices.length;
        while (true) {
            v = p + 1;
            while (v + 1 < n && prices[v] > prices[v + 1]) {
                v++;
            }
            p = v;
            while (p + 1 < n && prices[p] <= prices[p + 1]) {
                p++;
            }

            if (p == v) {
                break;
            }

            //新的交易的买入点更低，要把栈顶的元素出栈
            while (!stack.isEmpty() && prices[v] <= prices[stack.peek().valley]) {
                Transaction pop = stack.pop();
                profit.add(prices[pop.peek] - prices[pop.valley]);
            }

            //当前交易和栈顶交易是否能合并
            while (!stack.isEmpty() && prices[p] >= prices[stack.peek().peek]) {
                Transaction pop = stack.pop();
                profit.add(prices[pop.peek] - prices[v]);
                v = pop.valley;
            }

            stack.push(new Transaction(v, p));
        }

        while (!stack.isEmpty()) {
            Transaction pop = stack.pop();
            profit.add(prices[pop.peek] - prices[pop.valley]);
        }
        int ret = 0;
        if (k >= profit.size()) {
            for (int i = 0; i < profit.size(); i++) {
                ret += profit.get(i);
            }
        } else {
            Collections.sort(profit, new Comparator<Integer>() {
                @Override
                public int compare(Integer n1, Integer n2) {
                    return n2 - n1;
                }
            });

            for (int i = 0; i < k; i++) {
                ret += profit.get(i);
            }
        }
        return ret;
    }

}
